The dichromatic number of a graph $G$ is the maximum integer $k$ such thatthere exists an orientation of the edges of $G$ such that for every partitionof the vertices into fewer than $k$ parts, at least one of the parts mustcontain a directed cycle under this orientation. In 1979, Erd\H{o}s andNeumann-Lara conjectured that if the dichromatic number of a graph is bounded,so is its chromatic number. We make the first significant progress on thisconjecture by proving a fractional version of the conjecture. While our resultuses stronger assumption about the fractional chromatic number, it also gives amuch stronger conclusion: If the fractional chromatic number of a graph is atleast $t$, then the fractional version of the dichromatic number of the graphis at least $\tfrac{1}{4}t/\log_2(2et^2)$. This bound is best possible up to asmall constant factor. Several related results of independent interest aregiven.
展开▼
机译：图$ G $的双色数是最大整数$ k $，因此存在$ G $的边的方向，使得对于每个分割成少于$ k $个部分的顶点，至少必须包含一个部分在这种定向下的有向循环。 1979年，Erd \ H {o} s和Neumann-Lara推测，如果图的二色数是有界的，那么它的色数也是有界的。通过证明该猜想的一个分数形式，我们在该猜想上取得了第一个重大进展。虽然我们的结果对分数色数使用了更强的假设，但它也给出了更强的结论：如果图的分数色数至少为$ t $，则图的二色数的分数形式至少为$ \ tfrac {1 } {4} t / \ log_2（2et ^ 2）$。最好在一个较小的恒定因子范围内。给出了几个有关独立利益的结果。
展开▼
